package com.formula.datastructure.exercise.graph.undirect.sp;

// 代码用书上的最好 https://my.oschina.net/thinwonton/blog/3133222

import com.formula.datastructure.exercise.graph.undirect.ListEdge;
import com.formula.datastructure.exercise.graph.undirect.ListGraph;
import com.formula.datastructure.exercise.graph.undirect.MatrixGraph;
import com.formula.datastructure.util.DataUtil;


// Dij算的是某一个顶点到其他顶点的最短距离
// Dij推荐使用邻接矩阵
public class Dijkstra {

    // 不要用Max, 容易溢出成为负值
    private static final int INF = 99999;

    /**
     * 引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点
     * <p>
     * 一共有三块
     * #1 初始化, 把起始点自己加入到S顶点里面, 路径为0
     * #2 得到U, 也就是S里面的顶点连接的点
     * #3 每次在U里面去找最小的边, 对应的顶点引入新的S变化
     *
     * @param graph
     * @param start 只会计算所有点到start点的最短距离
     */
    public void shortestPath(MatrixGraph graph, int start) {
        // 也就是节点个数
        int N = graph.size;

        // 先要有三个数组, 分别记录是否已经访问, 前驱顶点, 从start顶点到该顶点距离
        int[] visited = new int[N];
        int[] prev = new int[N];
        int[] distance = new int[N];

        // 从start开始了
        visited[start] = 1;
        prev[start] = start;
        distance[start] = 0;

        // 初始化start的distance, 邻接矩阵应该在赋值上面保持一致, 比如用Max表示无连接
        for (int i = 0; i < N; i++) {
            distance[i] = graph.edges[start][i];
        }

        // 这里应该初始化, 因为默认0是不对的
        for (int i = 0; i < N; i++) {
            prev[i] = -1;
        }

        /**
         * 对于邻接矩阵, 下面就是逻辑核心
         */
        // 剩下n-1个顶点, 循环n-1次
        for (int k = 0; k < N - 1; k++) {
            /**
             * 先要把下一个顶点找出来, 下一个顶点满足
             * 1. 没访问过
             * 2. 距离start最近
             */
            int min = INF;
            int addedNode = start;
            for (int i = 0; i < N; i++) {
                if (visited[i] == 0 && distance[i] < min) {
                    min = distance[i];
                    addedNode = i;
                }
            }

            // 点已经找出来, 设置为已访问
            visited[addedNode] = 1;

            // 判断新的顶点是否需要更新distance
            for (int j = 0; j < N; j++) {
                // 所有访问过的都不用再访问, 如果一个点A到start的距离大于 A到New + New到start
                if (visited[j] == 0 && distance[j] > distance[addedNode] + graph.edges[addedNode][j]) {
                    distance[j] = distance[addedNode] + graph.edges[addedNode][j];
                    prev[j] = addedNode;
                }
            }
        }

        DataUtil.printArray(prev);
        DataUtil.printArray(distance);
    }

    public void shortestPath(ListGraph graph, int start) {
        // 也就是节点个数
        int nodeNum = graph.vertexSize();

        // 先要有三个数组, 分别记录是否已经访问, 前驱顶点, 从start顶点到该顶点距离
        int[] visited = new int[nodeNum];
        int[] prev = new int[nodeNum];
        // 如果是邻接表, 最后还是要换成邻接矩阵
        int[] distance = new int[nodeNum];

        // 从start开始了
        visited[start] = 1;
        prev[start] = start;
        distance[start] = 0;

        ListEdge tempEdge = graph.vertexList[start].firstEdge;
        int min = INF;
        int idx = start;

        // 这里其实就是把邻接表的内容填入distance
    }

    public static void main(String[] args) {
        MatrixGraph graph = new MatrixGraph();
        graph.insertVex("A");
        graph.insertVex("B");
        graph.insertVex("C");
        graph.insertVex("D");
        graph.insertVex("E");
        graph.insertVex("F");
        graph.insertVex("G");
        for (int i = 0; i < graph.size; i++) {
            //Arrays.fill(graph.edges[i], INF);
            graph.insertEdge(i, i, 0);
        }

        graph.insertEdge(0, 1, 5);
        graph.insertEdge(0, 2, 7);

        graph.insertEdge(1, 4, 4);
        graph.insertEdge(1, 5, 3);

        graph.insertEdge(2, 3, 6);
        graph.insertEdge(2, 6, 4);

        graph.insertEdge(3, 4, 4);
        graph.insertEdge(3, 5, 2);

        graph.insertEdge(4, 2, 8);
        graph.insertEdge(4, 6, 3);

        Dijkstra sp = new Dijkstra();
        sp.shortestPath(graph, 0);
    }

}
